package slidingWindow;

import java.util.ArrayList;
import java.util.List;

//https://leetcode.cn/problems/find-all-anagrams-in-a-string/
public class l_438 {
    public List<Integer> findAnagrams(String s, String p) {
        //正常做法是维护定长窗口的字符串哈希以及p字符串的哈希, 每次移动之后比较
        //如果是整个ASCII码的字符话常数较大
        //这里对两个哈希的比较进行优化, 引入变量统计"有效字符"
        int n = s.length(), count = 0, len = p.length();
        int[] hash1 = new int[128], hash2 = new int[128];
        List<Integer> ans = new ArrayList<Integer>();
        for(byte ch: p.getBytes()) ++hash2[ch];
        for(int left = 0, right = 0; right < n; ++right) {
            int in = s.charAt(right), out = s.charAt(left);
            if(++hash1[in] <= hash2[in]) ++count;
            if(right > len - 1) {
                if(hash1[out]-- <= hash2[out]) --count;
                ++left;
            }
            if(count == len) ans.add(left);
        }
        return ans;
    }
}
